//------------------------------------------------------------------
//	hash list implementation
//------------------------------------------------------------------
#include "Globals.h"
#include "hashlist.h"


//------------------------------------------------------------------
//	CStaticHashList
//	set the data
//------------------------------------------------------------------
void	CStaticHashList::SetData( u32 nItems, CHashListItem *pItems)
{
	m_nItems = nItems;
	m_pItems = pItems;
}

//------------------------------------------------------------------
//	CStaticHashList
//	does an item exist
//------------------------------------------------------------------
bool CStaticHashList::ItemExists( HASH hashValue, u32 *outIndex ) const
{
	s32		window[3];

	// empty???
	if( m_nItems==0 )
		return false;

	// simple binary search
	window[0] = 0;
	window[2] = m_nItems-1;
	while( window[0]<=window[2] )
	{
		window[1] = (window[0]+window[2])/2;

		// is this the item we're looking for?
		if( m_pItems[window[1]].hashValue==hashValue )
		{
			if( outIndex )
				outIndex[0] = window[1];
			return true;
		}

		// check whether to search top or bottom half of list
		if( m_pItems[window[1]].hashValue<hashValue )
			window[0] = window[1]+1;
		else
			window[2] = window[1]-1;
	}

	return false;
}

//------------------------------------------------------------------
//	CStaticHashList
//	find an entry by hash
//------------------------------------------------------------------
void *CStaticHashList::FindByHash( HASH hashValue ) const
{
	s32		window[3];

	// empty???
	if( m_nItems==0 )
		return 0;

	// simple binary search
	window[0] = 0;
	window[2] = m_nItems-1;
	while( window[0]<=window[2] )
	{
		window[1] = (window[0]+window[2])/2;

		// is this the item we're looking for?
		if( m_pItems[window[1]].hashValue==hashValue )
			return m_pItems[window[1]].data;

		// check whether to search top or bottom half of list
		if( m_pItems[window[1]].hashValue<hashValue )
			window[0] = window[1]+1;
		else
			window[2] = window[1]-1;
	}

	return 0;
}

//------------------------------------------------------------------
//	CStaticHashList
//	find an entry by index
//------------------------------------------------------------------
void *CStaticHashList::FindByIndex( u32 index ) const
{
	if( index>=m_nItems )
		return 0;
	return m_pItems[index].data;
}

//------------------------------------------------------------------
//	CStaticHashList
//	find a hash by index
//------------------------------------------------------------------
HASH CStaticHashList::FindHashByIndex( u32 index ) const
{
	if( index>=m_nItems )
		return 0;
	return m_pItems[index].hashValue;
}

//------------------------------------------------------------------
//	CStaticHashList
//	find the index where a given hash value should go
//	this is very similar to the FindByHash routine
//------------------------------------------------------------------
u32 CStaticHashList::FindIndexForHash( HASH hashValue )
{
	s32		window[3];

	if( m_nItems==0 )
		return 0;

	// simple binary search
	window[0] = 0;
	window[2] = m_nItems-1;
	while( window[0]<=window[2] )
	{
		window[1] = (window[0]+window[2])/2;

		// is this the item we're looking for?
		if( m_pItems[window[1]].hashValue==hashValue )
			return window[1];

		// check whether to search top or bottom half of list
		if( m_pItems[window[1]].hashValue<hashValue )
			window[0] = window[1]+1;
		else
			window[2] = window[1]-1;
	}

	// do we belong after this item?
	if( m_pItems[window[1]].hashValue<hashValue )
		window[1]++;
	return window[1];
}

//------------------------------------------------------------------
//	CHashList
//	sort items (static member function)
//------------------------------------------------------------------
int __cdecl hashSortFn( const void *a, const void *b )
{
	if( (((CHashListItem*)a)->hashValue) > (((CHashListItem*)b)->hashValue) )
		return 1;
	if( (((CHashListItem*)a)->hashValue) < (((CHashListItem*)b)->hashValue) )
		return -1;
	return 0;
}

void	CHashList::SortItems( u32 numItems, CHashListItem *pItems )
{
	qsort(pItems,numItems,sizeof(CHashListItem),hashSortFn);
}

//------------------------------------------------------------------
//	CHashList
//	destructor
//------------------------------------------------------------------
CHashList::~CHashList()
{
	Clear(true);
}

//------------------------------------------------------------------
//	CHashList
//	clear the hash list out
//------------------------------------------------------------------
void CHashList::Clear( bool freeMemory )
{
	m_nItems = 0;
	if( freeMemory && m_pItems )
	{
		m_maxItems = 0;
		free(m_pItems);
		m_pItems = 0;
	}
}

//------------------------------------------------------------------
//	CHashList
//	add an item to the hashlist
//------------------------------------------------------------------
bool CHashList::AddByHash( HASH hashValue, void *pData )
{
	u32				toIndex;
	CHashListItem	*pMe;

	// find where this hashValue goes
	toIndex = FindIndexForHash(hashValue);

	// is an item with this hash already here?
	if( toIndex!=m_nItems && m_pItems[toIndex].hashValue==hashValue )
		return false;

	// create room in the hash table
	if( m_nItems==m_maxItems )
	{	// need to reallocate some data
		m_maxItems += 32;	// allocate some more items
		m_pItems = (CHashListItem*)realloc(m_pItems,m_maxItems*sizeof(CHashListItem));
	}

	pMe = &m_pItems[toIndex];

	// make a hole for me to go
	if( toIndex!=m_nItems )
	{
		memmove( &pMe[1],pMe,(m_nItems-toIndex)*sizeof(CHashListItem));
	}

	pMe->hashValue = hashValue;
	pMe->data = pData;

	m_nItems++;
	return true;

}

//------------------------------------------------------------------
//	CHashList
//	remove an item to the hashlist
//------------------------------------------------------------------
bool CHashList::RemoveByHash( HASH hashValue )
{
	u32				toIndex;

	// find where this hashValue goes
	toIndex = FindIndexForHash(hashValue);

	// is an item with this hash here?
	if( toIndex==m_nItems || m_pItems[toIndex].hashValue!=hashValue )
		return false;

	// remove this item from the list
	m_nItems-=1;
	if( toIndex!=m_nItems )
	{
		memmove(&m_pItems[toIndex],&m_pItems[toIndex+1],(m_nItems-toIndex)*sizeof(CHashListItem));
	}
	return true;
}
